import java.util.*;

public class 最小基因变化 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> hash = new HashSet<>();//存储基因库
        Set<String> vis = new HashSet<>();//存储搜索过的字符串
        for(String x : bank){
            hash.add(x);
        }
        if(startGene.equals(endGene)){
            return 0;
        }
        if(!hash.contains(endGene)){
            return -1;
        }
        char[] s = {'A', 'C', 'G', 'T'};
        Queue<String> q = new LinkedList<>();
        q.add(startGene);
        vis.add(startGene);
        int step = 0;
        while(!q.isEmpty()){
            int sz = q.size();
            step++;
            while(sz-- > 0){
                String t = q.poll();
                for(int i = 0;i < 8;i++){
                    char[] str = t.toCharArray();
                    for(int j = 0;j < 4;j++){
                        str[i] = s[j];
                        String next = new String(str);
                        if(hash.contains(next) && !vis.contains(next)){
                            if(next.equals(endGene)){
                                return step;
                            }
                            vis.add(next);
                            q.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
